import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Back_Track {
    public List<String> generateParenthesis(int n) {
        List<String> result=new ArrayList<>();
        generateSubOne("",result,n,n);
        return result;
    }

    private void generateSubOne(String s, List<String> result, int n, int n1) {
        if(n>n1)return;
        if(n>0){
            generateSubOne(s+"(",result,n-1,n1);
        }
        if(n1>0){
            generateSubOne(s+")",result,n,n1-1);
        }
        if(n1==0&&n==0){
            result.add(s);
            return;
        }
    }


    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        boolean choose[]=new boolean[nums.length];
        List<Integer> node=new ArrayList<>();
        permuteOne(choose,result,node,nums.length,nums);
        return result;
    }

    private void permuteOne(boolean[] temp, List<List<Integer>> result, List<Integer> node, int length,int []nums) {
        if(length==0){
            result.add(new ArrayList<>(node));
        }else {
            for(int i=0,a=0;a<length;i++){
                if(!temp[i]){
                    temp[i]=true;
                    node.add(nums[i]);
                    int size=node.size();
                    permuteOne(temp,result,node,length-1,nums);
                    temp[i]=false;
                    node.remove(size-1);
                    a++;
                }
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        char[] c=digits.toCharArray();
        int len=c.length;
        List<String> list=new ArrayList<>();
        if(len==0) return list;
        String s="";
        char[][]data={{'a','b','c'},{'d','e','f'},{'g','h','i'},
                {'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},
                {'w','x','y','z'}};
        letterCombinationOne(list,c,s,0,len,data);
        return list;
    }
    private void letterCombinationOne(List<String> list, char[] c, String s, int i, int len, char[][] data) {
        if(i==len) {
            list.add(s);
            return;
        }
        else {
            int cur=c[i]-'2';
            int num=data[cur].length;
            for(int a=0;a<num;a++){
                letterCombinationOne(list,c,s+data[cur][a],i+1,len,data);
            }
        }
    }

    public boolean exist(char[][] board, String word) {
        if(board.length<=0) return false;
        int H=board.length;
        int W=board[0].length;
        boolean [][]visit=new boolean[H][W];
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++){
                if(dfs(board,word,0,i,j,visit))
                    return true;
            }
        return false;    
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visit) {
        if(index==word.length()){
            return true;
        }
        if(i<0||j<0||i>=board.length||j>=board[0].length){
            return false;
        }
        if(visit[i][j]){
            return false;
        }
        if(word.charAt(index)!=board[i][j]){
            return false;
        }
        visit[i][j]=true;
        boolean flag=dfs(board,word,index+1,i-1,j,visit)||dfs(board, word, index+1, i+1, j, visit)
                ||dfs(board, word, index+1, i, j-1, visit)||dfs(board, word, index+1, i, j+1, visit);
        visit[i][j]=false;
        return flag;
    }

}
